package main.Q401_500;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q411_420 {
	public static void main(String[] args) {
		System.out.println("Question411：");
		System.out.println("Question412：Fizz Buzz");
		System.out.println("Question413：等差数列划分");
		System.out.println("Question414：第三大的数");
		System.out.println("Question415：字符串相加");
		System.out.println("Question416：分割等和子集");
		System.out.println("Question417：太平洋大西洋水流问题");
		System.out.println("Question418：");
		System.out.println("Question419：甲板上的战舰");
		char[][] board = {{'X', '.', '.', 'X'}, {'.', '.', '.', 'X'}, {'.', '.', '.', 'X'}, {'.', '.', '.', '.'}};
		System.out.println(new Question419().countBattleships(board));
		System.out.println("Question420：");
	}
}

class Question412 {
	public List<String> fizzBuzz(int n) {
		List<String> list = new ArrayList<>();
		for (int i = 1; i <= n; i++) {
			if (i % 3 == 0 && i % 5 == 0) list.add("FizzBuzz");
			else if (i % 3 == 0 && i % 5 != 0) list.add("Fizz");
			else if (i % 3 != 0 && i % 5 == 0) list.add("Buzz");
			else list.add(String.valueOf(i));
		}
		return list;
	}
}

class Question413 {
	public int numberOfArithmeticSlices(int[] nums) {
		int length = nums.length, count = 0, left = 0, right = left + 2;//滑动窗口也可解决
		if (length < 3) return 0;
		while (right < length) {
			if (nums[right - 1] - nums[right - 2] == nums[right] - nums[right - 1] && right - left >= 2) {
				count++;//满足等差
				count += right - left - 3;//左边界移动可产生的等差数列
				right++;
			} else {
				if (right - left != 2) count += right - 1 - left - 2;
				left = right;
				right = left + 2;
			}
		}
//        if (right-left>2) count+=right-left-3;//有边界触底，仍存在等差数列
		return count;
//        int length=nums.length,count=0;//动态规划
//        int[][] dp=new int[length][length];
//        for (int i=0;i<length;i++){
//            for (int j=i+2;j<length;j++){
//                if (j-i==2&&nums[i+1]-nums[i]==nums[j]-nums[i+1]) dp[i][j]=1;//满足至少含有3个元素，且3个元素满足等差
//                else if (nums[j-1]-nums[j-2]==nums[j]-nums[j-1]&&dp[i][j-1]!=0) dp[i][j]=1;
//                if (dp[i][j]!=0) count+=dp[i][j];
//            }
//        }
//        return count;
	}
}

class Question414 {//未解决

	public int thirdMax(int[] nums) {
		Arrays.sort(nums);
		int third = nums[nums.length - 1], max = nums[nums.length - 1], count = 1;
		for (int i = nums.length - 1; i >= 0; i--) {
			if (count == 3) break;
			if (third != nums[i]) {
				count++;
				third = nums[i];
			}
		}
		if (count == 3) return third;
		else return max;
	}
}

class Question415 {
	public String addStrings(String num1, String num2) {
		int i = num1.length() - 1, j = num2.length() - 1, add = 0;
		StringBuffer result = new StringBuffer();
		while (i >= 0 || j >= 0 || add != 0) {
			int a = i >= 0 ? num1.charAt(i) - '0' : 0;
			int b = j >= 0 ? num2.charAt(j) - '0' : 0;
			result.append((a + b + add) % 10);
			add = (a + b + add) / 10;//判断是否需要进位
			i--;
			j--;
		}
		return result.reverse().toString();
	}
}

class Question416 {
	public boolean canPartition(int[] nums) {
		int m = 0;
		for (int num : nums) m += num;
		if (m % 2 != 0) return false;
		m /= 2;
		boolean[] dp = new boolean[m + 1];
		dp[0] = true;
		for (int x : nums) {
			for (int j = m; j >= x; j--) {
				dp[j] |= dp[j - x];
			}
		}
		return dp[m];
	}
}

class Question417 {
	static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	int[][] heights;
	int m, n;

	public List<List<Integer>> pacificAtlantic(int[][] heights) {
		this.heights = heights;
		this.m = heights.length;
		this.n = heights[0].length;
		boolean[][] pacific = new boolean[m][n];
		boolean[][] atlantic = new boolean[m][n];
		for (int i = 0; i < m; i++) {
			process(i, 0, pacific);
		}
		for (int j = 1; j < n; j++) {
			process(0, j, pacific);
		}
		for (int i = 0; i < m; i++) {
			process(i, n - 1, atlantic);
		}
		for (int j = 0; j < n - 1; j++) {
			process(m - 1, j, atlantic);
		}
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (pacific[i][j] && atlantic[i][j]) {
					List<Integer> cell = new ArrayList<Integer>();
					cell.add(i);
					cell.add(j);
					result.add(cell);
				}
			}
		}
		return result;
	}

	public void process(int row, int col, boolean[][] ocean) {
		if (ocean[row][col]) return;
		ocean[row][col] = true;
		for (int[] dir : dirs) {
			int newRow = row + dir[0], newCol = col + dir[1];
			if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]) {
				process(newRow, newCol, ocean);
			}
		}
	}
}

class Question419 {
	public void process(int row, int col, char[][] board) {
		board[row][col] = '.';
		if (row + 1 < board.length && board[row + 1][col] == 'X') {//向下
			int temp = row + 1;
			while (temp < board.length && board[temp][col] == 'X') {
				board[temp][col] = '.';
				temp++;
			}
		}
		if (col + 1 < board[0].length && board[row][col + 1] == 'X') {//向右
			int temp = col + 1;
			while (temp < board[0].length && board[row][temp] == 'X') {
				board[row][temp] = '.';
				temp++;
			}
		}
	}

	public int countBattleships(char[][] board) {
		int count = 0;
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				if (board[i][j] == 'X') {
					count++;
					process(i, j, board);
				}
			}
		}
		return count;
	}
}